/**
 * 一个3L的杯子和一个5L的杯子，怎样倒出来4L水？
 * 输出最短的路径
 */

#include <iostream>
#include <vector>
#include <complex>
#include <optional>

using std::cout;
using std::cin;
using std::vector;
using std::complex;
using std::optional;

class Road {             // Road类记录一条路径
public:
    void add_operator(int origin, int destination) { road.emplace_back(origin, destination); }
    void print() const;        // 输出这条路径
    bool operator<(const Road& other) const { return road.size()<other.road.size(); }
private:
    vector<complex<int>> road;
};

class Condition {          // Condition类记录一个水量状态
public:
    Condition() : cup3L{}, cup5L{}, road_length{} { }
    bool pour(int origin, int destination);        // 从origin杯倒向destination杯。返回是否成功倒水。origin为1=3L杯，2=5L杯。destination为2=5L杯，1=3L杯，0=倒空，-1=倒满
    bool repeat(const Condition& other) const { return cup3L==other.cup3L and cup5L==other.cup5L and road_length>=other.road_length; }
    bool success() const { return cup5L==4; }
private:
    int cup3L;
    int cup5L;
    int road_length;
};

Road exhaust(const Condition& condition =Condition{}, const Road& road =Road{});             // 递归穷举倒水结果

int main(int argc, char** argv)
{
    cout.sync_with_stdio(false);
    Road road {exhaust()};
    road.print();
    cin.get();
    return 0;
}

Road exhaust(const Condition& condition, const Road& road)
{
    static optional<Road> result;
    static vector<Condition> conditions;
    if (condition.success())
        if (not result or road<*result) {
            result = road;
            return road;
        }
    for (auto& c : conditions)
        if (condition.repeat(c))
            return *result;
    conditions.push_back(condition);
    for (int origin{1}; origin<=2; ++origin)
        for (int dest{2}; dest>=-1; --dest) {
            Condition copy_condition {condition};
            Road copy_road {road};
            if (not copy_condition.pour(origin, dest))
                continue;
            copy_road.add_operator(origin, dest);
            exhaust(copy_condition, copy_road);
        }
    return *result;
}

bool Condition::pour(int origin, int destination)
{
    if (origin == destination)
        return false;
    bool inside {true};
    int* from {&cup3L};
    int* to {&cup5L};
    int to_capacity {5};
    switch (destination) {
    case 1:
        from = &cup5L;
        to = &cup3L;
        to_capacity = 3;
        break;
    case 0:
    case -1:
        inside = false;
        if (origin == 1)
            to_capacity = 3;
        else
            from = &cup5L;
        break;
    }
    if (inside) {
        int diff {to_capacity-*to};
        if (diff**from == 0)
            return false;
        if (diff > *from)
            diff = *from;
        *from -= diff;
        *to += diff;
    }
    else
        *from = ((destination==0) ? 0 : to_capacity);
    ++road_length;
    return true;
}

void Road::print() const
{
    for (const auto& r : road) {
        cout << ((r.real()==1) ? 3 : 5) << "L杯 -> ";
        switch (r.imag()) {
        case 2:
        case 1:
            cout << ((r.imag()==1) ? 3 : 5) << "L杯";
            break;
        case 0:
            cout << "倒空";
            break;
        case -1:
            cout << "倒满";
            break;
        }
        cout << '\n';
    }
}
